The invention relates generally to the art of digital communications and more specifically to a system for minimizing the average latency in transporting messages, such as packets or frames, which are segmented into a plurality of smaller cells for transport across a network.
Asynchronous transfer mode (hereinafter xe2x80x9cATMxe2x80x9d) service inter-networking protocols enable data or messages formatted according to a non-ATM data communication protocol to be transported across an ATM network. For example, the Frame Relay Forum FRF.5 protocol specifies how a relatively large, variable length, frame relay packet should be segmented into a plurality of ATM-like, fixed-size, cells for transport across an ATM network. Such protocols necessarily define how the ATM Adaption Layer (AAL) should be provisioned since this layer of the ATM/B-ISDN protocol stack, as defined by ITU Recommendation I.321 and shown in FIG. 1, is responsible for adapting the services provided by the ATM Layer, which provides basic ATM cell transport functions, to higher layers, e.g. frame-up relay bearer service.
FIG. 2 illustrates a generic version of the AAL in greater detail. As shown in FIG. 2, some versions of the AAL, such as AAL3/4 and AAL5, include a convergence sublayer (CS) and a segmentation and reassembly sublayer (SAR). The CS, which sits directly above the SAR and below the AAL Service Access Point (SAP), aligns the SDUs and adds overhead information. The CS may also provide service specific signalling or data link functions.
The SAR, when operating in a message mode, segments a single AAL SAR Service Data Unit (hereinafter xe2x80x9cSDUxe2x80x9d), such as a variable length frame packet, into a plurality of AAL SAR Protocol Data Units (hereinafter xe2x80x9cPDUxe2x80x9d), each of which essentially forms the payload of an ATM cell transmitted across an ATM network. Conversely, at the destination, the destination SAR requires that all of the PDUs composing an SDU be passed from the ATM Layer to the destination SAR before it can reassemble the SDU and, ignoring the role of the convergence sublayer, indicate reception of the SDU to the higher layer using the AAL. Thus, the latency in transmitting an SDU from a first point to a second point in a network can be defined as the time from which the transmission of the SDU is first requested until the time the last PDU arrives at the destination SAR and the SDU is reassembled. In other words, latency can be defined as the time required to transmit the SDU from an originating AAL SAP to a destination AAL SAP. This latency is entirely characterized by the amount of time required to propagate the last PDU of an SDU across the ATM networkxe2x80x94the time required to propagate any other PDU before the last PDU of an SDU is of no consequence at the destination AAL SAP.
Latency manifests itself as sluggishness or slow response time in interactive-type communications. For example, if one were sending joystick instructions across a network during the course of an interactive game played there over, a long latency would, in the absence of other aggravating factors, result in a noticeable time period between the physical movement of the joystick and the corresponding computer action. Accordingly, it is desirable to minimize latency for interactive telecommunications applications.
Latency is affected by the service discipline used to schedule or multiplex PDUs corresponding to SDUs from a plurality of virtual connections (VCs) into a single cell stream for transmission across the Physical Layer (PHY) of the ATM network. FIG. 3 shows how an ATM Layer 11 provides a SAP 10 to each of several VCs, each of which has its own AAL 12 (i.e., the AAL is invoked in parallel instances). The ATM Layer 11, in turn, uses a single SAP 14 into a PHY 16. One role of the ATM Layer 11 is to accept requests of PDUs 17 from each SAP 10 and to multiplex these PDUs into a single cell stream 18 such that the timing of the transmission of each of the PDUs conforms to predetermined traffic parameters assigned to its respective VC.
FIG. 3 illustrates a condition where each VC generates a burst 20 of several ATM PDU requests at the ATM SAP 10, wherein each such burst corresponds to a single SDU 22, such that there is an overlap in the transmission periods of the SAR SDUs from the ATM Layer 11 to the PHY 16. The ATM PDUs 17 received from the ATM SAP 10 must therefore be queued, and then the ATM PDUs from each of the different ATM SAPs 10 must be multiplexed in some order onto the single stream 18 of ATM PDUs passed to the PHY SAP 14. Given this set of PDUs which have been requested over several ATM Layer SAPs 10, and subject to the constraints of satisfying the traffic parameters of each VC, it is often desired to minimize the average amount of latency experienced per unit of SDU data (i.e., per PDU) for various types of ATM service categories.
As shown in FIG. 3, a typical ATM Layer implementation might use round-robin ordering in sending the PDUs 17 to the PHY SAP 14 from each ATM SAP 10. This would result in each corresponding SDU 22 using an equal fraction of the PHY bandwidth while the PDUs for each SDU are being transmitted. This is shown, for instance, in the bandwidth occupancy chart of FIG. 4A for the situation where two VCs each request a burst of the same number of PDUs at about the same time, wherein each VC has a PCR equal to 100% of the available bandwidth. (A xe2x80x9cbandwidth occupancy chartxe2x80x9d is a chart with time on the horizontal axis, and bandwidth on the vertical axis. Each SDU sent on an ATM virtual connection is shown as a shaded region on such a chart. The net height of the region at a particular time shows the amount of bandwidth occupied by the transmission of the SDU at that time; the leftmost and rightmost extent of the region gives the time at which the first and last PDUs for the SDU are transmitted, respectively; and the total area of the region gives the size of the SDU. Unshaded regions in these charts represent the proportion of unused PHY bandwidth, for which the ATM Layer will be sending idle cells.) This ordering is not optimal with respect to the average amount of latency experienced per unit of SDU data.
Broadly speaking, the invention seeks to minimize or reduce the average per unit latency in transporting messages which are decomposed into a plurality of smaller data units for transport across a network.
One aspect of the invention relates to an apparatus for transmitting messages associated with a plurality of connections. The apparatus comprises transmission equipment for receiving multiple messages, segmenting each received message into one or more data units, and multiplexing such data units from various connections into a single stream for transport over a physical interface at an output transmission rate. A bandwidth allocation means is associated with the transmission equipment for dynamically allocating a portion of the output transmission rate to any connection. A scheduler is connected to the bandwidth allocation means for scheduling the transfer of messages to the single stream of the transmission equipment and for allocating a substantially maximum permissible portion of the output transmission rate to each connection substantially at the time its message is transferred to the transmission equipment in order to minimize interleaving of data units from various connections.
The transmission equipment preferably comprises a segmentation means and a multiplexing means for respectively segmenting each received message into the aforesaid data units and multiplexing same to the single stream of data units associated with the transmission equipment. The scheduler preferably transfers messages to the single stream by receiving the messages directly from higher layer networking services and transferring the messages to the segmentation means which, in turn, substantially immediately transfers the messages to the multiplexing means. Alternatively, the scheduler transfers messages to the single stream by receiving the data units from the segmentation means and transferring groups of data units to the multiplexing means, wherein each such group corresponds to a message.
The scheduler is also preferably enabled to additionally set the transmission rate for each connection whose message is in the process of being transmitted to the maximum permissible portion of the output transmission rate during the message transmission. The maximum permissible portion of the output transmission rate for a given connection at any given time is the lessor of (i) a pre-specified peak transmission rate for the given connection and (ii) all unused bandwidth at the given time allocated to a service class to which the given connection belongs.
The scheduler, upon reception of a given message associated with a given connection, is also preferably enabled to transfer the given message to the single stream of data units provided free bandwidth is available for the given connection and provided that the given connection does not have a previous message in the process of being transmitted by the transmission equipment. In the event no free bandwidth is available for the given connection or in the event that the given connection has a previous message in the process of being transmitted by the transmission equipment, the scheduler is enabled to queue the given message at the end of a queue of pending data messages.
The apparatus also preferably includes indication means, connected to the scheduler, for indicating when a last data unit of a message has been transmitted by the transmission equipment. When the indication means is actuated, the scheduler is enabled to increase the transmission rate of any connection in the process of having a message being transmitted by the transmission equipment provided that free bandwidth is available for the given connection.
A preferred embodiment of the invention relates to an ATM communications device wherein the messages are ATM adaption layer (AAL) service data units (SDUs) associated with a plurality of virtual circuit connections. The data units are AAL segmentation and reassembly protocol data units (SAR PDUs). The transmission equipment preferably comprises segmentation means for segmenting each AAL SDU into one or more SAR PDUs, ATM layer means for multiplexing the SAR PDUs of various connections into a single stream having an output transmission rate, and physical transmission means, connected to the ATM layer means, for transporting the single stream of SAR PDUs over a physical interface. In the preferred embodiment, bandwidth allocation means are provided to dynamically allocate a portion of the output transmission rate to any connection. The scheduler, which is connected to the bandwidth allocation means, is responsible for scheduling the transfer of SDUs to the ATM layer means and for allocating a substantially maximum permissible portion of the output transmission rate to each connection substantially at the time its SDU is submitted to the ATM layer means in order to minimize interleaving of SAR PDUs from various connections in the single stream. The scheduler also preferably allocates a maximal portion of the output transmission rate to a connection while an SDU associated therewith is in the process of being transmitted by the ATM layer means. The scheduler transfers SDUs to the ATM layer means by receiving the SDUs from AAL users and transferring the SDUs to the segmentation means which substantially immediately transfers the SAR PDUs to the ATM layer means. Alternatively, the scheduler may transfer SDUs to the ATM layer means by transferring groups of SAR PDUs to the ATM layer means, wherein each such group corresponds to an SDU.
Another aspect of the invention provides a data transmission method for transporting multiple messages associated with multiple connections over a network. The method comprises the steps of: (a) segmenting each message of each connection into transportable data units; (b) scheduling the transfer of messages from the multiple connections to a multiplexing step; (c) multiplexing the data units from various connections into a single stream for transport over a transmission media to a destination; and (d) assigning a maximum permissible amount of transmission media bandwidth to each connection at the time a message thereof substantially begins to be transported over the transmission media, thereby minimizing interleaving of data units from the multiple connections over the transmission media. The method also preferably includes the step of setting the bandwidth for a connection whose message is in the process of being transmitted to the maximum permissible amount during the transmission of the message.